//547. 省份数量

//有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
//省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
//给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
//返回矩阵中 省份 的数量。

//class Solution {
//public:
//    int findCircleNum(vector<vector<int>>& isConnected) {
//        int cities = isConnected.size();
//        vector<int8_t> visited(cities);
//        int provinces = 0;
//        queue<int> q;
//        for (int i = 0; i < cities; i++) {
//            if (!visited[i]) {
//                q.push(i);
//                while (!q.empty()) {
//                    int& j = q.front();
//                    visited[j] = 1;
//                    for (int k = 0; k < cities; k++) {
//                        if (isConnected[j][k] == 1 && !visited[k]) {
//                            q.push(k);
//                        }
//                    }
//                    q.pop();
//                }
//                provinces++;
//            }
//        }
//        return provinces;
//    }
//};

//1971. 寻找图中是否存在路径

//有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，
//其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
//请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
//给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

//class Solution {
//public:
//    bool dfs(int source, int destination, vector<vector<int>>& adj, vector<int8_t>& visited) {
//        if (source == destination) {
//            return true;
//        }
//        visited[source] = true;
//        for (int next : adj[source]) {
//            if (!visited[next] && dfs(next, destination, adj, visited)) {
//                return true;
//            }
//        }
//        return false;
//    }
//
//    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
//        vector<vector<int>> adj(n);
//        for (auto& edge : edges) {
//            int x = edge[0], y = edge[1];
//            adj[x].emplace_back(y);
//            adj[y].emplace_back(x);
//        }
//        vector<int8_t> visited(n);
//        return dfs(source, destination, adj, visited);
//    }
//};

//797. 所有可能的路径

//给你一个有 n 个节点的 有向无环图（DAG），请你找出从节点 0 到节点 n - 1 的所有路径并输出（不要求按特定顺序）
//graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

//class Solution {
//public:
//    vector<vector<int>> ans;
//    vector<int> stk;
//
//    void dfs(vector<vector<int>>& graph, int x, int n) {
//        if (x == n) {
//            ans.push_back(stk);
//            return;
//        }
//        for (auto& y : graph[x]) {
//            stk.push_back(y);
//            dfs(graph, y, n);
//            stk.pop_back();
//        }
//    }
//
//    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//        stk.push_back(0);
//        dfs(graph, 0, graph.size() - 1);
//        return ans;
//    }
//};

//841. 钥匙和房间

//有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
//当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
//给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

//class Solution {
//public:
//    bool canVisitAllRooms(vector<vector<int>>& rooms) {
//        int n = rooms.size(), num = 0;
//        vector<int8_t> vis(n);
//        queue<int> que;
//        vis[0] = true;
//        que.emplace(0);
//        while (!que.empty()) {
//            int x = que.front();
//            que.pop();
//            num++;
//            for (auto& it : rooms[x]) {
//                if (!vis[it]) {
//                    vis[it] = true;
//                    que.emplace(it);
//                }
//            }
//        }
//        return num == n;
//    }
//};

//2316. 统计无向图中无法互相到达点对数

//给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
//请你返回 无法互相到达 的不同 点对数目 。

//class Solution {
//public:
//    long long countPairs(int n, vector<vector<int>>& edges) {
//        vector<vector<int>> g(n);
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            g[x].push_back(y);
//            g[y].push_back(x);
//        }
//
//        vector<int8_t> vis(n);
//        auto dfs = [&](this auto&& dfs, int x) -> int {
//            vis[x] = true;
//            int size = 1;
//            for (int y : g[x]) {
//                if (!vis[y]) {
//                    size += dfs(y);
//                }
//            }
//            return size;
//            };
//
//        long long ans = 0;
//        for (int i = 0, total = 0; i < n; i++) {
//            if (!vis[i]) {
//                int size = dfs(i);
//                ans += static_cast<long long>(size) * total;
//                total += size;
//            }
//        }
//        return ans;
//    }
//};

//1319. 连通网络的操作次数

//用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n - 1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
//网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
//给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。
//请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 - 1 。

//class Solution {
//private:
//    vector<vector<int>> edges;
//    vector<int8_t> used;
//
//public:
//    void dfs(int u) {
//        used[u] = true;
//        for (int v : edges[u]) {
//            if (!used[v]) {
//                dfs(v);
//            }
//        }
//    }
//
//    int makeConnected(int n, vector<vector<int>>& connections) {
//        if (connections.size() < n - 1) {
//            return -1;
//        }
//
//        edges.resize(n);
//        for (const auto& conn : connections) {
//            edges[conn[0]].push_back(conn[1]);
//            edges[conn[1]].push_back(conn[0]);
//        }
//
//        used.resize(n);
//        int ans = 0;
//        for (int i = 0; i < n; ++i) {
//            if (!used[i]) {
//                dfs(i);
//                ++ans;
//            }
//        }
//
//        return ans - 1;
//    }
//};

//2492. 两个城市间路径的最小分数

//给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，
//其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条 双向 道路，道路距离为 distancei 。城市构成的图不一定是连通的。
//两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。
//城市 1 和城市 n 之间的所有路径的 最小 分数。
//注意：
//一条路径指的是两个城市之间的道路序列。
//一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
//测试数据保证城市 1 和城市n 之间 至少 有一条路径。

//class Solution {
//public:
//    int minScore(int n, vector<vector<int>>& roads) {
//        // 建图
//        vector<int> e[n + 1], v[n + 1];
//        for (auto& road : roads) {
//            e[road[0]].push_back(road[1]);
//            v[road[0]].push_back(road[2]);
//            e[road[1]].push_back(road[0]);
//            v[road[1]].push_back(road[2]);
//        }
//
//        int ans = 1e9;
//        queue<int> q;
//        vector<int8_t> vis(n + 1);
//        memset(vis, 0, sizeof(vis));
//        q.push(1); vis[1] = true;
//        while (!q.empty()) {
//            int sn = q.front(); q.pop();
//            for (int i = 0; i < e[sn].size(); i++) {
//                ans = min(ans, v[sn][i]);
//                int fn = e[sn][i];
//                if (vis[fn]) continue;
//                q.push(fn); vis[fn] = true;
//            }
//        }
//
//        return ans;
//    }
//};

//3310. 移除可疑的方法

//你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。
//给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。
//已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法都被视为 可疑方法 ，我们需要从项目中移除这些方法。
//只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。
//返回一个数组，包含移除所有 可疑方法 后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除 所有 可疑方法，则 不 移除任何方法。

//class Solution {
//public:
//    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
//        vector<vector<int>> g(n);
//        for (auto& e : invocations) {
//            g[e[0]].push_back(e[1]);
//        }
//
//        // 标记所有可疑方法
//        vector<int8_t> is_suspicious(n);
//        auto dfs = [&](auto&& dfs, int x) -> void {
//            is_suspicious[x] = true;
//            for (int y : g[x]) {
//                if (!is_suspicious[y]) {
//                    dfs(dfs, y);
//                }
//            }
//            };
//        dfs(dfs, k);
//
//        // 检查是否有非可疑方法->可疑方法的边
//        for (auto& e : invocations) {
//            if (!is_suspicious[e[0]] && is_suspicious[e[1]]) {
//                // 无法移除可疑方法
//                vector<int> ans(n);
//                iota(ans.begin(), ans.end(), 0);
//                return ans;
//            }
//        }
//
//        // 移除所有可疑方法
//        vector<int> ans;
//        for (int i = 0; i < n; i++) {
//            if (!is_suspicious[i]) {
//                ans.push_back(i);
//            }
//        }
//        return ans;
//    }
//};

//2685. 统计完全连通分量的数量

//给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。
//返回图中 完全连通分量 的数量。
//如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。
//如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。

//class Solution {
//public:
//    int countCompleteComponents(int n, vector<vector<int>>& edges) {
//        vector<vector<int>> g(n);
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            g[x].emplace_back(y);
//            g[y].emplace_back(x);
//        }
//
//        vector<int8_t> vis(n);
//        int ans = 0, v, e;
//        auto dfs = [&](this auto&& dfs, int x) {
//            vis[x] = true;
//            v++;
//            e += g[x].size();
//            for (int y : g[x])
//                if (!vis[y])
//                    dfs(y);
//            };
//
//        for (int i = 0; i < n; i++) {
//            if (!vis[i]) {
//                v = 0;
//                e = 0;
//                dfs(i);
//                ans += e == v * (v - 1);
//            }
//        }
//        return ans;
//    }
//};

//2192. 有向无环图中一个节点的所有祖先

//给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
//给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
//请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
//如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

//class Solution {
//public:
//    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
//        vector<vector<int>> g(n);
//        for (auto& e : edges) {
//            g[e[0]].emplace_back(e[1]);
//        }
//
//        vector<vector<int>> ans(n);
//        vector<int> vis(n, -1);
//        int start;
//        function<void(int)> dfs = [&](int x) {
//            vis[x] = start;
//            for (int y : g[x]) {
//                if (vis[y] != start) {
//                    ans[y].emplace_back(start);
//                    dfs(y);
//                }
//            }
//            };
//        for (start = 0; start < n; start++) {
//            dfs(start);
//        }
//        return ans;
//    }
//};

//3387. 两天自由外汇交易后的最大货币数

//给你一个字符串 initialCurrency，表示初始货币类型，并且你一开始拥有 1.0 单位的 initialCurrency。
//另给你四个数组，分别表示货币对（字符串）和汇率（实数）：
//pairs1[i] = [startCurrencyi, targetCurrencyi] 表示在 第 1 天，可以按照汇率 rates1[i] 将 startCurrencyi 转换为 targetCurrencyi。
//pairs2[i] = [startCurrencyi, targetCurrencyi] 表示在 第 2 天，可以按照汇率 rates2[i] 将 startCurrencyi 转换为 targetCurrencyi。
//此外，每种 targetCurrency 都可以以汇率 1 / rate 转换回对应的 startCurrency。
//你可以在 第 1 天 使用 rates1 进行任意次数的兑换（包括 0 次），然后在 第 2 天 使用 rates2 再进行任意次数的兑换（包括 0 次）。
//返回在两天兑换后，最大可能拥有的 initialCurrency 的数量。
//注意：汇率是有效的，并且第 1 天和第 2 天的汇率之间相互独立，不会产生矛盾。

//class Solution {
//public:
//    double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
//        auto calc_amount = [&](vector<vector<string>>& pairs, vector<double>& rates) {
//            unordered_map<string, vector<pair<string, double>>> g;
//            for (int i = 0; i < pairs.size(); i++) {
//                auto& p = pairs[i];
//                double r = rates[i];
//                g[p[0]].emplace_back(p[1], r);
//                g[p[1]].emplace_back(p[0], 1 / r);
//            }
//
//            unordered_map<string, double> amount;
//            auto dfs = [&](this auto&& dfs, const string& x, double cur_amount) -> void {
//                amount[x] = cur_amount;
//                for (auto& [to, rate] : g[x]) {
//                    // 每个节点只需递归一次
//                    if (!amount.contains(to)) {
//                        dfs(to, cur_amount * rate);
//                    }
//                }
//                };
//            dfs(initialCurrency, 1);
//            return amount;
//            };
//
//        auto day1_amount = calc_amount(pairs1, rates1);
//        auto day2_amount = calc_amount(pairs2, rates2);
//
//        double ans = 0;
//        for (auto& [x, a2] : day2_amount) {
//            ans = max(ans, day1_amount[x] / a2);
//        }
//        return ans;
//    }
//};

//924. 尽量减少恶意软件的传播

//给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
//一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
//这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
//假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
//如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
//请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

//class Solution {
//public:
//    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
//        set<int> st(initial.begin(), initial.end());
//        vector<int8_t> vis(graph.size());
//        int ans = -1, max_size = 0, node_id, size;
//        auto dfs = [&](this auto&& dfs, int x) -> void {
//            vis[x] = true;
//            size++;
//            // 按照状态机更新 node_id
//            if (node_id != -2 && st.contains(x)) {
//                node_id = node_id == -1 ? x : -2;
//            }
//            for (int y = 0; y < graph[x].size(); y++) {
//                if (graph[x][y] && !vis[y]) {
//                    dfs(y);
//                }
//            }
//            };
//
//        for (int x : initial) {
//            if (vis[x]) {
//                continue;
//            }
//            node_id = -1; // 为x有一个感染点，-2为多个
//            size = 0;
//            dfs(x);
//            if (node_id >= 0 && (size > max_size || size == max_size && node_id < ans)) {
//                ans = node_id;
//                max_size = size;
//            }
//        }
//        return ans < 0 ? ranges::min(initial) : ans;
//    }
//};

//2101. 引爆最多的炸弹

//给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
//炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
//你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
//给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

//class Solution {
//public:
//    int maximumDetonation(vector<vector<int>>& bombs) {
//        int n = bombs.size();
//        vector<vector<int>> g(n);
//        for (int i = 0; i < n; i++) {
//            long long x = bombs[i][0], y = bombs[i][1], r = bombs[i][2];
//            for (int j = 0; j < n; j++) {
//                long long dx = x - bombs[j][0];
//                long long dy = y - bombs[j][1];
//                if (j != i && dx * dx + dy * dy <= r * r) {
//                    g[i].push_back(j); // i 可以引爆 j
//                }
//            }
//        }
//
//        int ans = 0;
//        vector<int8_t> vis(n);
//        auto dfs = [&](auto&& dfs, int x) -> int {
//            vis[x] = true;
//            int cnt = 1;
//            for (int y : g[x]) {
//                if (!vis[y]) {
//                    cnt += dfs(dfs, y);
//                }
//            }
//            return cnt;
//            };
//        for (int i = 0; i < n && ans < n; i++) {
//            ranges::fill(vis, 0);
//            ans = max(ans, dfs(dfs, i));
//        }
//        return ans;
//    }
//};

//721. 账户合并

//给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称(name)，其余元素是 emails 表示该账户的邮箱地址。
//现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。
//请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。
//一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
//合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

//class Solution {
//public:
//    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
//        int n = accounts.size();
//        unordered_map<string, vector<int>> email_to_idx;
//        for (int i = 0; i < n; i++) {
//            for (int k = 1; k < accounts[i].size(); k++) {
//                email_to_idx[accounts[i][k]].emplace_back(i);
//            }
//        }
//
//        unordered_set<string> email_set; // 用于收集 DFS 中访问到的邮箱地址
//        vector<int8_t> vis(n);
//        auto dfs = [&](this auto&& dfs, int i) -> void {
//            vis[i] = true;
//            for (int k = 1; k < accounts[i].size(); k++) { // 遍历 i 的所有邮箱地址
//                string& email = accounts[i][k];
//                if (email_set.contains(email)) {
//                    continue;
//                }
//                email_set.insert(email);
//                for (int j : email_to_idx[email]) { // 遍历所有包含该邮箱地址的账户下标 j
//                    if (!vis[j]) { // j 没有访问过
//                        dfs(j);
//                    }
//                }
//            }
//            };
//
//        vector<vector<string>> ans;
//        for (int i = 0; i < vis.size(); i++) {
//            if (vis[i]) {
//                continue;
//            }
//            email_set.clear();
//            dfs(i);
//
//            vector<string> res = { accounts[i][0] };
//            res.insert(res.end(), email_set.begin(), email_set.end());
//            sort(res.begin() + 1, res.end());
//
//            ans.emplace_back(res);
//        }
//        return ans;
//    }
//};

//207. 课程表

//你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//例如，先修课程对[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

//class Solution {
//public:
//    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { // 判断是否有环
//        vector<vector<int>> g(numCourses);
//        for (auto& p : prerequisites) {
//            g[p[1]].emplace_back(p[0]);
//        }
//
//        vector<int8_t> colors(numCourses);
//        // 返回 true 表示找到了环
//        auto dfs = [&](this auto&& dfs, int x) -> bool {
//            colors[x] = 1; // x 正在访问中
//            for (int y : g[x]) {
//                if (colors[y] == 1 || colors[y] == 0 && dfs(y)) {
//                    return true; // 找到了环
//                }
//            }
//            colors[x] = 2; // x 完全访问完毕，从 x 出发无法找到环
//            return false; // 没有找到环
//            };
//
//        for (int i = 0; i < numCourses; i++) {
//            if (colors[i] == 0 && dfs(i)) {
//                return false; // 有环
//            }
//        }
//        return true; // 没有环
//    }
//};

//802. 找到最终的安全状态

//有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。
//图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。
//如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点（或另一个安全节点），则该节点为 安全节点。
//返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。

//class Solution {
//public:
//    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
//        int n = graph.size();
//        vector<int8_t> color(n); // 0:未访问, 1:访问中, 2:安全
//        auto dfs = [&](this auto&& dfs, int i) -> bool {
//            if (color[i]) return color[i] == 2;
//            color[i] = 1;
//            for (int& x : graph[i]) {
//                if (!dfs(x)) {
//                    return false;
//                }
//            }
//            color[i] = 2;
//            return true;
//            };
//        vector<int> ans;
//        for (int i = 0; i < n; i++) {
//            if (dfs(i)) {
//                ans.emplace_back(i);
//            }
//        }
//        return ans;
//    }
//};

//928. 尽量减少恶意软件的传播 II

//给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
//一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
//这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
//假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
//我们可以从 initial 中 删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
//请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

//class Solution {
//public:
//    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
//        int n = graph.size();
//        unordered_set<int> st(initial.begin(), initial.end());
//        vector<int8_t> vis(n);
//        int node_id, size;
//        auto dfs = [&](this auto&& dfs, int x) -> void {
//            vis[x] = true;
//            size++;
//            for (int y = 0; y < graph[x].size(); y++) {
//                if (graph[x][y] == 0) {
//                    continue;
//                }
//                if (st.contains(y)) {
//                    if (node_id != -2 && node_id != y) {
//                        node_id = node_id == -1 ? y : -2;
//                    }
//                }
//                else if (!vis[y]) {
//                    dfs(y);
//                }
//            }
//            };
//
//        unordered_map<int, int> cnt;
//        for (int i = 0; i < n; i++) {
//            if (vis[i] || st.contains(i)) {
//                continue;
//            }
//            node_id = -1;
//            size = 0;
//            dfs(i);
//            if (node_id >= 0) { // 只找到一个在 initial 中的节点
//                // 删除节点 node_id 可以让 size 个点不被感染
//                cnt[node_id] += size;
//            }
//        }
//
//        int max_cnt = 0;
//        int min_node_id = 0;
//        for (auto& [node_id, c] : cnt) {
//            if (c > max_cnt || c == max_cnt && node_id < min_node_id) {
//                max_cnt = c;
//                min_node_id = node_id;
//            }
//        }
//        return cnt.empty() ? ranges::min(initial) : min_node_id;
//    }
//};

//2092. 找出知晓秘密的所有专家

//给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，
//其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
//专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。
//更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
//秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
//在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

//class Solution {
//public:
//    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
//        ranges::sort(meetings, [&](const auto& v1, const auto& v2) {
//            return v1[2] < v2[2];
//            });
//        unordered_set<int> haveSecret = { 0, firstPerson };
//        int m = meetings.size();
//        for (int i = 0; i < m;) {
//            unordered_map<int, vector<int>> g;
//            int& time = meetings[i][2];
//            for (; i < m && meetings[i][2] == time; i++) {
//                int& a = meetings[i][0], & b = meetings[i][1];
//                g[a].emplace_back(b);
//                g[b].emplace_back(a);
//            }
//            auto dfs = [&](this auto&& dfs, int v) -> void {
//                haveSecret.insert(v);
//                for (int& w : g[v]) {
//                    if (!haveSecret.count(w)) {
//                        dfs(w);
//                    }
//                }
//                };
//
//            for (auto& [v, _] : g) {
//                if (haveSecret.count(v)) {
//                    dfs(v);
//                }
//            }
//        }
//        vector<int> ans;
//        for (auto& v : haveSecret)
//            ans.emplace_back(v);
//        return ans;
//    }
//};

//3108. 带权图里旅途的最小代价

//给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。
//给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。
//在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。
//如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, ..., wk ，
//那么代价为w0& w1& w2 & ... & wk ，其中& 表示按位与 AND 操作。
//给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 - 1 。
//返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。

//class Solution {
//    vector<int> fa, and_;
//
//    int find(int x) {
//        return fa[x] == x ? x : fa[x] = find(fa[x]);
//    };
//
//public:
//    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
//        fa.resize(n);
//        ranges::iota(fa, 0);
//        and_.resize(n, -1);
//        for (auto& e : edges) {
//            int x = find(e[0]);
//            int y = find(e[1]);
//            and_[y] &= e[2];
//            if (x != y) {
//                and_[y] &= and_[x];
//                fa[x] = y;
//            }
//        }
//
//        vector<int> ans;
//        ans.reserve(query.size()); // 预分配空间
//        for (auto& q : query) {
//            int s = q[0], t = q[1];
//            ans.emplace_back(find(s) != find(t) ? -1 : and_[find(s)]);
//        }
//        return ans;
//    }
//};

//1298. 你能从盒子里获得的最大糖果数

//给你 n 个盒子，每个盒子的格式为[status, candies, keys, containedBoxes] ，其中：
//状态字 status[i]：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。
//糖果数 candies[i]: 整数，表示 box[i] 中糖果的数目。
//钥匙 keys[i]：数组，表示你打开 box[i] 后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。
//内含的盒子 containedBoxes[i]：整数，表示放在 box[i] 里的盒子所对应的下标。
//给你一个整数数组 initialBoxes，包含你最初拥有的盒子。你可以拿走每个 已打开盒子 里的所有糖果，并且可以使用其中的钥匙去开启新的盒子，并且可以使用在其中发现的其他盒子。
//请你按照上述规则，返回可以获得糖果的 最大数目 。

//class Solution {
//public:
//    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
//        int ans = 0;
//        auto& has_key = status; // 把开着的盒子当作有钥匙
//        vector<uint8_t> has_box(status.size());
//        for (int x : initialBoxes) {
//            has_box[x] = true;
//        }
//
//        auto dfs = [&](this auto&& dfs, int x) -> void {
//            ans += candies[x];
//            has_box[x] = false; // 避免找到钥匙后重新访问开着的盒子
//
//            // 找到钥匙，打开盒子（说明我们先找到盒子，然后找到钥匙）
//            for (int y : keys[x]) {
//                has_key[y] = true;
//                if (has_box[y]) {
//                    dfs(y);
//                }
//            }
//
//            // 找到盒子，使用钥匙（说明我们先找到钥匙，然后找到盒子）
//            for (int y : containedBoxes[x]) {
//                has_box[y] = true;
//                if (has_key[y]) {
//                    dfs(y);
//                }
//            }
//            };
//
//        for (int x : initialBoxes) {
//            if (has_key[x] && has_box[x]) { // 注意 dfs 中会修改 has_box
//                dfs(x);
//            }
//        }
//        return ans;
//    }
//};

//3243. 新增道路查询后的最短距离 I

//给你一个整数 n 和一个二维整数数组 queries。
//有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
//queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
//返回一个数组 answer，对于范围[0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

//class Solution {
//public:
//    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
//        vector<vector<int>> g(n - 1);
//        for (int i = 0; i < n - 1; i++) {
//            g[i].emplace_back(i + 1);
//        }
//        vector<int> vis(n - 1, -1);
//
//        auto bfs = [&](int i) -> int {
//            vector<int> q = { 0 };
//            for (int step = 1; ; step++) {
//                vector<int> nxt;
//                for (int x : q) {
//                    for (int y : g[x]) {
//                        if (y == n - 1) {
//                            return step;
//                        }
//                        if (vis[y] != i) {
//                            vis[y] = i;
//                            nxt.emplace_back(y);
//                        }
//                    }
//                }
//                q = move(nxt);
//            }
//            };
//
//        vector<int> ans(queries.size());
//        for (int i = 0; i < queries.size(); i++) {
//            g[queries[i][0]].emplace_back(queries[i][1]);
//            ans[i] = bfs(i);
//        }
//        return ans;
//    }
//};

//1311. 获取你好友已观看的视频

//有 n 个人，每个人都有一个  0 到 n - 1 的唯一 id 。
//给你数组 watchedVideos  和 friends ，其中 watchedVideos[i]  和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。
//Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。
//一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。
//给定你的 id  和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。

//using PSI = pair<string, int>;
//
//class Solution {
//public:
//    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
//        int n = friends.size();
//        vector<int8_t> used(n);
//        queue<int> q;
//        q.emplace(id);
//        used[id] = true;
//        for (int _ = 1; _ <= level; ++_) {
//            int span = q.size();
//            for (int i = 0; i < span; ++i) {
//                int& u = q.front();
//                for (int v : friends[u]) {
//                    if (!used[v]) {
//                        q.emplace(v);
//                        used[v] = true;
//                    }
//                }
//                q.pop();
//            }
//        }
//
//        unordered_map<string, int> freq;
//        while (!q.empty()) {
//            int& u = q.front();
//            for (const string& watched : watchedVideos[u]) {
//                ++freq[watched];
//            }
//            q.pop();
//        }
//
//        vector<PSI> videos(freq.begin(), freq.end());
//        ranges::sort(videos, [](const PSI& p, const PSI& q) {
//            return p.second < q.second || (p.second == q.second && p.first < q.first);
//            });
//
//        vector<string> ans;
//        for (const PSI& video : videos) {
//            ans.emplace_back(video.first);
//        }
//        return ans;
//    }
//};

//1129. 颜色交替的最短路径

//给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。
//给定两个数组 redEdges 和 blueEdges，其中：
//redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边，
//blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。
//返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

//class Solution {
//public:
//    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
//        vector<vector<int>> next(n * 2);
//        for (auto& e : redEdges) {
//            next[0 + e[0]].emplace_back(e[1]);
//        }
//        for (auto& e : blueEdges) {
//            next[n + e[0]].emplace_back(e[1]);
//        }
//
//        vector<int> dist(n * 2, 0x3f3f3f3f); // 两种类型的颜色最短路径的长度
//        queue<pair<int, int>> q;
//        dist[0] = 0;
//        dist[n] = 0;
//        q.emplace(0, 0);
//        q.emplace(0, 1);
//        while (!q.empty()) {
//            auto& [x, t] = q.front();
//            for (auto y : next[(1 - t) * n + x]) {
//                if (dist[(1 - t) * n + y] != 0x3f3f3f3f) {
//                    continue;
//                }
//                dist[(1 - t) * n + y] = dist[t * n + x] + 1;
//                q.emplace(y, 1 - t);
//            }
//            q.pop();
//        }
//        vector<int> ans(n);
//        for (int i = 0; i < n; i++) {
//            ans[i] = min(dist[i], dist[n + i]);
//            if (ans[i] == 0x3f3f3f3f) {
//                ans[i] = -1;
//            }
//        }
//        return ans;
//    }
//};

//2039. 网络空闲的时刻

//给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，
//在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。
//题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
//编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，
//也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。
//在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：
//如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，
//也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
//否则，该数据服务器 不会重发 信息。
//当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
//请返回计算机网络变为 空闲 状态的 最早秒数 

//class Solution {
//public:
//    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
//        int n = patience.size();
//        vector<vector<int>> adj(n);
//        vector<int8_t> visit(n);
//        for (auto& v : edges) {
//            adj[v[0]].emplace_back(v[1]);
//            adj[v[1]].emplace_back(v[0]);
//        }
//
//        queue<int> qu;
//        qu.emplace(0);
//        visit[0] = true;
//        int dist = 1;
//        int ans = 0;
//        while (!qu.empty()) {
//            int sz = qu.size();
//            for (int i = 0; i < sz; ++i) {
//                int curr = qu.front();
//                qu.pop();
//                for (auto& v : adj[curr]) {
//                    if (visit[v]) {
//                        continue;
//                    }
//                    qu.emplace(v);
//                    int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
//                    ans = max(ans, time);
//                    visit[v] = true;
//                }
//            }
//            dist++;
//        }
//        return ans;
//    }
//};

//2608. 图中的最短环

//现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，
//其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。
//返回图中 最短 环的长度。如果不存在环，则返回 - 1 。
//环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

//class Solution {
//public:
//    int findShortestCycle(int n, vector<vector<int>>& edges) {
//        vector<vector<int>> g(n);
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            g[x].push_back(y);
//            g[y].push_back(x); // 建图
//        }
//
//        int dis[n]; // dis[i] 表示从 start 到 i 的最短路长度
//        auto bfs = [&](int start) -> int {
//            int ans = INT_MAX;
//            memset(dis, -1, sizeof(dis));
//            dis[start] = 0;
//            queue<pair<int, int>> q;
//            q.emplace(start, -1);
//            while (!q.empty()) {
//                auto [x, fa] = q.front();
//                q.pop();
//                for (int y : g[x])
//                    if (dis[y] < 0) { // 第一次遇到
//                        dis[y] = dis[x] + 1;
//                        q.emplace(y, x);
//                    }
//                    else if (y != fa) // 第二次遇到
//                        ans = min(ans, dis[x] + dis[y] + 1);
//            }
//            return ans;
//            };
//        int ans = INT_MAX;
//        for (int i = 0; i < n; ++i) // 枚举每个起点跑 BFS
//            ans = min(ans, bfs(i));
//        return ans < INT_MAX ? ans : -1;
//    }
//};

//815. 公交路线

//给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
//例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
//现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
//求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 - 1 。

//class Solution {
//public:
//    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
//        // 记录经过车站 x 的公交车编号
//        unordered_map<int, vector<int>> stop_to_buses;
//        for (int i = 0; i < routes.size(); i++) {
//            for (int x : routes[i]) {
//                stop_to_buses[x].emplace_back(i);
//            }
//        }
//
//        // 如果没有公交车经过起点或终点，直接返回
//        if (!stop_to_buses.contains(source) || !stop_to_buses.contains(target)) {
//            return source != target ? -1 : 0;
//        }
//
//        unordered_map<int, int> dis;
//        dis[source] = 0;
//        queue<int> q;
//        q.emplace(source);
//        while (!q.empty()) {
//            int x = q.front(); // 当前在车站 x
//            q.pop();
//            int dis_x = dis[x];
//            for (int i : stop_to_buses[x]) { // 遍历所有经过车站 x 的公交车 i
//                for (int y : routes[i]) { // 遍历公交车 i 的路线
//                    if (!dis.contains(y)) { // 没有访问过车站 y
//                        dis[y] = dis_x + 1; // 从 x 站上车然后在 y 站下车
//                        q.emplace(y);
//                    }
//                }
//                routes[i].clear(); // 标记 routes[i] 遍历过
//            }
//        }
//
//        return dis.contains(target) ? dis[target] : -1;
//    }
//};